class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        #dp0[i] 第i天手上没有股票时的最大收益, dp0[i] = max(dp0[i-1], dp1[i-1]+nums[i])
        #dp1[i] 第i天手上有股票时的最大收益, dp1[i] = max(dp1[i-1], dp0[i-1]-nums[i])
        dp0 = 0
        dp1 = -prices[0]
        for i in range(1, len(prices)):
            tmp = max(dp0, dp1+prices[i])
            dp1 = max(dp1, dp0-prices[i])
            dp0 = tmp
        return dp0
